package demo.DataStrucAndAlgo.Linked;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/23-07-23-14:02
 * @Description：demo.DataStrucAndAlgo  非环形链表的尾结点的next域指向根节点，环形-单向-普通类-循环-无头
 * 可解决Josephu(约瑟夫、约瑟夫环)问题
 * Josephu问题为:设编号为1，2，… n的n个人围坐一圈，约定编号为k (1<=k<=n)的人从1开始报数，
 * 数到m 的那个人出列，它的下一位又从1开始报数，数到m 的那个人又出列，
 * 依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
 */
class CNode{
    private int data;
    private CNode next;

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public CNode getNext() {
        return next;
    }

    public void setNext(CNode next) {
        this.next = next;
    }

    public CNode (int no){
        this.data = no;
    }

    @Override
    public String toString() {
        return "CNode{" +
                "data=" + data +
                '}';
    }
}
class CirleLinkedList{
    private CNode root;
    public CNode getRoot(){
        return root;
    }
    /*
    add方法：是否为第一个结点，是就自成一环-->不是就遍历到最后-->向环中插入结点
     */
    public void add(CNode newNode){
        if(root == null){          //当添加第一个结点时自成一环
            root = newNode;
            root.setNext(root);
            return;
        }
        CNode temp = root;
        while(temp.getNext() != root){       //循环遍历到环的最后
            temp = temp.getNext();
        }
        temp.setNext(newNode);     //向环中插入结点
        newNode.setNext(root);
    }
    public void show(){
        if(root == null){
            System.out.println("链表为空");
            return;
        }
        CNode temp = root;
//        System.out.println(temp.toString());
//        while(temp.getNext() != root){
//            System.out.println(temp.getNext().toString());
//            temp = temp.getNext();
//        }
        while(true){
            System.out.println(temp);
            if(temp.getNext() == root){
                break;
            }
            temp = temp.getNext();
        }
    }
    /*
    AutoAdd方法：也就是一个循环里面每次自动创建结点后调用add方法添加，建立从1-n的顺序环链
     */
    public void AutoAdd(int num){
        if(num < 1){        //数量不足1， 无法形成环
            return;
        }
        CNode cnode;
        for (int i = 1; i <= num; i++) {
            cnode = new CNode(i);
            add(cnode);
        }
    }

    /**
     * count方法：用于解决约瑟夫问题，通过建立两个辅助结点（temp,select）。
     *     先移动开始结点数-1次，使select移动到开始的结点处，后移动开始结点数-2次，
     *     使temp移动到select之后，通过定数循环，在每轮循环后打印select结点，
     *     并将select向后一位，利用temp删除刚刚被选中的结点即可
     * @param all   总人数
     * @param startNo    从第几个人开始
     * @param num  数多少下
     */
    public void count(int all, int startNo, int num){
        if (root == null || startNo < 1 || startNo > all){     //输入验证
            System.out.println("输入参数有误");
            return;
        }
        //需要两个辅助结点，用于确定被选中人，和被选中人的前一个人，便于结点删除
        CNode temp = root;
        CNode select = root;

        for(int i = 0; i < startNo-1; i++){      //先移动startNo-1次，使select移动到开始的结点处
            select = select.getNext();
        }
        for (int i = 0; i < startNo-2; i++) {     //后移动start-2次，使temp移动到select之前
            temp = temp.getNext();
        }
        while (true){     //模拟报数选人
            if(temp == select){     //只剩一个人了
                System.out.printf("幸运儿为：%d\n",select.getData());
                break;
            }
            for (int j = 0; j < num - 1; j++) {        //自己也要报数，所以-1
                temp = temp.getNext();
                select = select.getNext();
            }
            System.out.printf("编号%d的被选中\n",select.getData());
            //删除被选中结点
            select = select.getNext();
            temp.setNext(select);
        }
    }
}
public class CirleLinked {
    public static void main(String[] args) {
        CirleLinkedList cLink=new CirleLinkedList();
//        cLink.add(new CNode(1));
//        cLink.add(new CNode(2));
//        cLink.add(new CNode(3));
//        cLink.add(new CNode(4));
        cLink.AutoAdd(10);
        cLink.show();
        cLink.count(10,2,3);
    }
}
